BST Deletion | Data Structure | Pusan National University

자식 노드 0개부모 노드의 참조를 None으로 비운다.

자식 노드 1개부모 노드가 하나뿐인 자식 노드를 직접 가리키게 한다. 참조 하나만 바꾸므로 O(1)이다.

자식 노드 2개오른쪽 부분 트리의 최솟값인 후계 노드의 키와 값을 옮겨 적고, 후계 노드를 앞의 두 경우로 지운다.

후계 노드의 자식후계 노드는 최솟값이라 왼쪽 자식 노드가 없으므로 자식 노드가 없거나 오른쪽 하나뿐이다.

지울 노드의 자식 노드 수가 삭제 절차를 정한다

삭제 예를 고르고 진행한 단계를 옮기면 트리의 연결, 단계 기록, 중위 순회가 함께 바뀐다. 앞의 세 예는 강의의 20, 30, 50 삭제이고, 마지막 예는 일곱 노드 트리에서 루트가 아닌 30을 지운다.

삭제 예

진행한 단계 0

초록 원이 이번 단계에서 다루는 노드, 옅은 파란 원과 초록 선이 내려간 경로, 초록 테두리 원이 지울 노드다. 흐린 점선 원은 곧 떼어낼 원래 후계 노드이고, 초록 원 옆 줄 그은 수는 옮겨 적기 전의 키다. 아래 표는 단계마다 한 일이며 초록 행이 현재 단계다.

자식 노드가 둘인 노드를 고르고 빈자리를 채울 노드를 바꾸면 찾아가는 경로, 옮겨 오는 키, 삭제 뒤 트리 모양이 바뀐다. 선행 노드(predecessor)는 왼쪽 부분 트리의 최댓값이다.

지울 키

빈자리를 채울 노드

왼쪽은 지우기 전, 오른쪽은 지운 뒤다. 왼쪽에서 초록 테두리 원이 지울 노드, 옅은 파란 원과 초록 선이 빈자리를 채울 노드까지 내려간 경로, 초록 원이 그 노드다. 오른쪽에서 초록 원은 키가 바뀐 자리이고 초록 선은 splice로 새로 이은 참조다.